Лемма о числе границ

Ребро $e$ плоского графа $(G, \Gamma)$ принадлежит границе ровно одной его грани, если оно является мостом в $G$, и границе ровно двух граней, если не является мостом.

Поскольку изображение $\Gamma$ правильное, найдется область плоскости, пересекающаяся с $\Gamma$ в точности по образу ребра $e$. Все точки «верхней половины» этой области принадлежат одной и той же грани $F_1$, а все точки «нижней половины» — другой грани $F_2$. Ребро $e$ не принадлежит границе никаких других граней, кроме $F_1$ и $F_2$. Таким образом, лемма эквивалентна утверждению: $F_1 = F_2 \iff e$ является мостом. **Доказательство необходимости:** От противного: Пусть $e$ не мост. Тогда по свойству моста ребро $e$ лежит в цикле, а значит, и в простом цикле. Изображение простого цикла — это замкнутая кривая, которая делит плоскость на внутреннюю и внешнюю области. Любая линия, соединяющая точки из разных областей, пересекает эту кривую. Следовательно, одна из граней, $F_1$ или $F_2$, лежит во внутренней области, а другая — во внешней. Отсюда следует, что $F_1 \neq F_2$. **Доказательство достаточности:** Пусть $e$ — мост. Тогда по свойству моста граф $G-e$ состоит из двух компонент связности, $G'$ и $G''$. Изображение одной компоненты находится внутри грани изображения другой, либо изображения компонент находятся во внешней грани друг друга. В любом случае, у изображений $G'$ и $G''$ нет общих точек. Следовательно, можно провести замкнутую кривую, внутри которой находится изображение $G'$, а снаружи — $G''$. При «возвращении» ребра $e$ на место, точки из областей $F_1$ и $F_2$ остаются соединенными фрагментом этой кривой, который не пересекает ребра графа. Следовательно, они принадлежат одной и той же грани, то есть $F_1 = F_2$. $\square$